\chapter{Methodology}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sub-Table of Content
%  1- Background
%  2- Architecture
%  3- Algorithms
%  4- Implementation
%  5- Controls
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Background

\section{Background}

\subsection{System Calls}

In computer systems, the \emph{kernel} is the main component of the
operating system. It is the piece of software in charge of managing
the system resources (i.e. communicating with the hardware
devices). Being the lowest abstraction layer between software and
hardware, every operation needing support from the underlying hardware
or requesting to update the hardware's state will go through it.

Thus, applications that need to access the hardware use the
\emph{kernel} layer interface: the \emph{system calls} (commonly
called \emph{syscalls}). \emph{Syscalls} are functions invoked by user
applications to request some service or resource from the
\emph{kernel} \cite{love:LINUXSYSPROG}.

With this in mind, it is obvious that it is possible to have a
complete monitoring of what applications request to do with the
resources of the computer system by adding logging mechanisms at the
entrance and exit of these functions.

\subsection{Scheduler}

We have seen that we can monitor access to the computer system's
resources by simply logging the usage of the \emph{kernel}
\emph{syscalls}. However, due to the nature of the \emph{kernel}, we
need to capture log from other parts of the \emph{kernel} to be able
to draw a timeline of an application's execution, namely the ones in
charge of allocating time slices to applications: the
\emph{scheduler}. The \emph{scheduler} is the part of the
\emph{kernel} deciding who can access the CPU at a given moment in
time and for how long. While a system gives the illusion of having
several applications running concurrently - multi-processor systems
aside - actually only one single process can make use of the CPU at
any given moment. The \emph{scheduler} allocates a tiny amount of time
to each application which leads to this illusion of concurrency
\cite{bovet:ULK}.

\subsection{Memory Mapping}

Monitoring \emph{syscalls} permits to see easily every change made to
files on disk. However, modern \emph{kernel}s give the possibility to
an application to map files in memory by using the mmap
\emph{syscall}. This allows an application to access directly the
content of a file as if it was part of its own memory space
(i.e. without having to issue the corresponding \emph{syscall} when it
needs to read or write to it). It also permits to reduce the
performance impact on data manipulation and moves by avoiding the
intermediate copy of the data in a \emph{kernel} buffer. Every time
the application will try to access a part of the file not yet mapped
into memory, the system will emit a so-called Page Fault. This event
will suspend the application execution and inform the \emph{kernel}
that the application tried to read or write a yet unmapped
position. Then the \emph{kernel} will load the relevant data into
memory and allow the application to resume its execution, starting
over from the point preceding the \emph{Page Fault}. The application
can now read or write from or to the portion of the file as
intended. In order to log the data modified and accessed by this kind
of application, it is thus necessary to alter the part of the
\emph{kernel} in charge of handling Page Faults in addition to the
logging of the mmap related \emph{syscalls}.

Because these file portions are loaded using the granularity of a
so-called \emph{Page Size} (usually 4 Kilobytes), the logging
mechanism is bound to use the same. This is translated by the fact
that the logging of the changes made to a portion of the file can only
be done when the application is removed from the CPU by the
\emph{scheduler}. Doing so earlier would not guarantee that every
changes made to a given portion (page) of the file will be logged.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Architecture

\section{Architecture}

\begin{figure}
  \centering
  \includegraphics[scale=0.40]{images/architecture/lemona-architecture-5.eps}
  \caption{Lemona's Architecture}
  \label{fig:fig4}
\end{figure}

\textbf{Lemona} is a compound of several components (Figure
\ref{fig:fig3} and Figure \ref{fig:fig4}), separated in three
categories:

\begin{figure}
  \centering
  \includegraphics[scale=0.55]{images/architecture/lemona-architecture-components.eps}
  \caption{Lemona's Components}
  \label{fig:fig5}
\end{figure}

\subsection{Monitoring Components}

\subsubsection{Kernel Patches}

These are alterations to the Linux Kernel codebase needed to monitor
\emph{syscalls} entry and exit points, as well as application
scheduling and memory mapped files related \emph{Page Faults}. The
patches are designed to allow a literate user to remove the
\textbf{Lemona} functionalities (and thus their processing overhead
and memory footprint) from the \emph{kernel} if he chooses to disable
it upon compilation.

\subsubsection{Loadable Kernel Modules}

While the patches add code at key \emph{kernel} points for logging,
the driver does the actual logging. It structures the logged
information and sends the result to the various designated
backends. Even Though we made it possible to dynamically load and
unload the \textbf{Lemona} functionalities, we only did so to
facilitate debugging and initial testing, or for end-users
convenience. However, administrators of production systems should
build the module statically for security reasons. This will for
instance avoid some early logs to be lost.

So far, the modules can only transmit the generated logs via two
different methods:

\begin{itemize}
  \item Via an (un)encrypted socket
  \item Via the kernel's relay functionality
\end{itemize}

It is important to note that data can easily be lost using any of
these techniques. In the first case, if the server does not answer or
is too slow to treat the data, incoming log data will be simply
drop. The same applies to the relay facility. Once the buffers are
full, new incoming logs will be discarded until the user application
processes enough data to free up one or more buffers.

\paragraph{Socket Method}

Upon startup, the module will prompt the user for the passphrase used
to encrypt sent to the logging server. Alternatively, this passphrase
could be stored on the local file system for automatic startup; but
this increase the security risk. If the link to the server is
considered sure enough, it is possible to disable the encryption
mechanism and thus reduce the CPU consumption impact of
\textbf{Lemona}.

\paragraph{Kernel Relay Method}

This method exists mainly for testing purposes. Using the relay
functionality of the \emph{kernel}, the logs are made available to
user space applications using the debugfs file system. User
applications are then free to transfer the data back to a logging
server or on a local database.

\subsection{Logging Components}

\subsubsection{Databases Servers}

SQL databases are used to stock the logs, making it easy for forensics
expert to query them and request specific data. This allows for quick
access to relevant informational datasets, and for easy and flexible
narrowing of the search domain (e.g. by date, applications,
etc...). Depending on the database server used on the backend, useful
requests could be recorded for future reference. In addition, we plan
to rely heavily on database caching mechanisms to speed up information
retrieval.

\subsubsection{Logging Servers}

This application is in charge of receiving the logs from the
\emph{kernel}. Upon startup, the \textbf{Lemona} driver will connect
to the logging server and start sending him data as it comes
through. In order to maximize throughput, the server should preferably
be directly connected to the monitoring machine via a fast link
(i.e. Gigabit Ethernet). For security reasons, the machine hosting the
server should be hardened, and avoid unnecessary services should be
disabled and uninstalled altogether.

The server application is actually a compound of two programs. The
first one is in charge of receiving the data sent by the driver. It
immediately appends the data to a set of buffer files without any
modification. Once a file is full, another one is created. The second
application will read already filled files, decrypt them and insert
the data in the database. This architecture avoids heavy slowdowns
upon data reception by delegating the load of the logs processing and
decryption (if any) on the receiving application.

\subsection{Forensics Component}

\subsubsection{Database-Querying Applications}

We are currently working on a querying application to provide simple
interactive access to the database data. This application should
permit the creation of specific queries without the user having to
know the database schema. It would present the output in a meaningful
way targeted at forensics expert.

This part of the \textbf{Lemona} architecture is still under heavy
R\&D though.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Algorithms

\section{Algorithms}

\subsection{Vocabulary}

\begin{itemize}
  \item \textbf{zest}: Name given to a single log entry generated by \textbf{Lemona}
  \item \textbf{blade}: Name given to the function in charge of processing a given \emph{syscall} argument type (e.g. integer, string, iovec, ...)
  \item \textbf{mixer}: Name given to the data structure describing which \emph{blades} should be used for a given \emph{syscall} argument and how many of those are expected upon entrance and exit
  \item \textbf{mixers}: Name of the array containing the mixer or all existing \emph{syscalls}
\end{itemize}

\subsection{Init}

On init \textbf{Lemona} simply call the initialization method of every
enabled backend. If none of them manage to initialize properly, the
loading of lemona is interrupted. This done, a variable
(\verb=lemona_activated=) is atomically set to signal that
\textbf{Lemona} can now be invoked for logging purpose.

\subsection{Hooks}

From the hook point of view, little is done. A check is made on
\verb=lemona_activated= to assert the fact that the logging facility
is active and if \textbf{Lemona} has been built as an external module
the logging method address is retrieved using the \textbf{kallsyms}
kernel facility.

\subsection{Logging}

\textbf{Lemona} logging works in a simple but nevertheless effective
way. Upon each monitored \emph{syscall} entry or exit, a counter
variable (\verb=lemona_clients=) indicated are many concurrent logging
are undertaken is first atomically incremented then the
\verb=lemona_log_{in,out}= is called with the system call number and
its arguments. Lemona will then fetch the corresponding entry for this
\emph{syscall} in the \emph{mixers} array. The creation of a
\emph{zest} is done in two phases:

\begin{enumerate}
  \item The \emph{blades} are invoked to determine how much space is needed for a given argument
  \item The \emph{blades} are invoked to copy the argument data in the \emph{zest}
\end{enumerate}

Once the \emph{zest} have been created, it is passed to every logging
backend supported by \textbf{Lemona}. It is important to note that the
success of these backends is not tested, since little can be done upon
error; the backends will, however, report the problems by printing a
succinct message in the logs.

\subsection{Unloading}

To avoid crash during the unloading process, the
\verb=lemona_activated= variable is first unset then \textbf{Lemona}
will wait until all logging activity currently executed finish they
work by checking the \verb=lemona_clients= variable. The actual
cleanup being made once this value reach zero.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Implementation

\section{Implementation}

\lstset{language=C,basicstyle=\footnotesize,tabsize=2}

A set of macros (figure \ref{listing:Macros}) are used when patching
\emph{syscall} in order to call \textbf{Lemona} logging
facilities. They principal advantage is to ease the reading of the
patched code. All actions related with the logging will be enclosed
inside the macros \verb=lemona_block_start= and
\verb=lemona_block_end=.

\begin{figure}
  \begin{centering}
    \begin{lstlisting}
extern atomic_t                 lemona_activated;
static lemonalogfn              _lemona_log     = NULL;

#  define lemona_block_start                                            \
  if (atomic_read(&lemona_activated) != 0)                              \
    {

#  define lemona_log_in(sysnr, argnr, extnr, ...)                       \
  __lemona_log(sysnr, true, argnr, extnr, ## __VA_ARGS__)

#  define lemona_log_out(sysnr, argnr, extnr, ...)                      \
  __lemona_log(sysnr, false, argnr, extnr, ## __VA_ARGS__)

#  define lemona_block_end                                              \
    }                                                                   \
  else {                                                                \
      _lemona_log = NULL;                                               \
    }

#  define __lemona_log(sysnr, in, argnr, extnr, ...) {                  \
  if (_lemona_log == NULL)                                              \
    _lemona_log = (lemonalogfn)kallsyms_lookup_name("lemona_log");      \
  _lemona_log(sysnr, in, argnr, extnr, ## __VA_ARGS__);                 \
}
    \end{lstlisting}
    \caption{Lemona's Logging Macros}
    \label{listing:Macros}
  \end{centering}
\end{figure}

As for the definition of a \emph{zest} it is quiet simple (figure
\ref{listing:Zest}). Common values are defined directly within the
structure whereas the others are expected to be find following the end
of the structure. To facilitate the access to the data following the
structure the \verb=argsz=, \verb=args=, \verb=extsz= and \verb=exts=
pointer are used during logging althought they had a little
unnecessary weight to the structure; they might be removed later.

\begin{figure}
  \begin{centering}
    \begin{lstlisting}
struct  lemona_zest {
  /*
    need always to be the first member. This facilitate parsing since a
    zest can find itself cut across two log files
   */
  int           size;   /* size taken by this zest and args sz/value    */
  char          magic[4];/* magic number                                */

  int           in;     /* input or output ?                            */
  struct timespec       time;   /* call start/end time (getnstimeofday) */

  pid_t         pid;    /* actual pid                                   */
  pid_t         tgid;   /* thread group id                              */

  uid_t         uid,euid,fsuid; /* user identification numbers          */
  gid_t         gid,egid,fsgid; /* group identification numbers         */

  int           sysnr;  /* syscall id                                   */
  int           argnr;  /* number of args                               */

  int           *argsz; /* ptr to an array of int giving each arg size  */
  void          *args;  /* ptr to the first argument of the array       */

  int           extnr;  /* extra value number                           */
  int           *extsz; /* size of each extension                       */
  void          *exts;  /* extra values. located after the last arg     */
} __attribute__((packed));
    \end{lstlisting}
    \caption{Lemona's Zest Structure}
    \label{listing:Zest}
  \end{centering}
\end{figure}


To create such a \emph{zest}, \textbf{Lemona} relies on a set of what
we call a \emph{mixer} (figure \ref{listing:Mixer}). It is a structure
compound of three data members:

\begin{enumerate}
  \item \verb=sysnr=: \emph{syscall} number affiliated to this \emph{mixer}
  \item \verb=in=: values to be used when logging entry to a \emph{syscall}
  \item \verb=out=: values to be used when logging exit from a \emph{syscall}
\end{enumerate}

The \verb=in= and \verb=out= data fields are themselves data structure
containing information about the number of arguments needed by the
logging method for this given \emph{syscall} and which \emph{blade} to
use to process each of them.

\begin{figure}
  \begin{centering}
    \begin{lstlisting}
struct  lemona_mixer {
  int                           sysnr;  /* system call number           */
  struct __lemona_mixer         in;     /* call entrance mixer          */
  struct __lemona_mixer         out;    /* call exit mixer              */
};

struct  __lemona_mixer {
  int                           argnr;  /* number of syscall parameters */
  int                           extnr;  /* number of extra parameters   */
  struct __lemona_mixer_handler handlers[6];    /* pre-defined handlers */
};

struct  __lemona_mixer_handler {
  bool                          dual;   /* is this a dual blade?        */
  bladefn                       blade;  /* number of extra  parameters  */
};

typedef int     (*bladefn)(struct lemona_zest *zest,    /* zest to fill */
                           int                isExt,    /* is an extra? */
                           int                idx,      /* param index  */
                           int                off,      /* mem. offset  */
                           void               *fruit1,  /* 1st data arg */
                           void               *fruit2); /* 2nd data arg */
    \end{lstlisting}
    \caption{Lemona's Mixer Structure}
    \label{listing:Mixer}
  \end{centering}
\end{figure}

To facilitate the retrieving of the mixer needed for a given
\emph{syscall}, we packed them in single read-only array
\emph{lemona\_mixers}. The entry for the \verb=open= \emph{syscall} is
given in figure \ref{listing:OpenMixer}. For this \emph{syscall} three
arguments are logged upon entry:

\begin{enumerate}
  \item The path to the file being opened (a user null terminated string)
  \item The access rights requested (an integer)
  \item The mode of creation if the file is to be created (an integer)
\end{enumerate}

Upon exit, two things need to be recorded:

\begin{enumerate}
  \item The return value of the syscall (an integer)
  \item The resolved path (a string obtained from the file descriptor returned by the \emph{syscall} when sucessful)
\end{enumerate}

The later is qualified as un ``external'' argument since it is not
part of the parameter of the \verb=open= \emph{syscall}

\begin{figure}
  \begin{centering}
    \begin{lstlisting}
const struct lemona_mixer       lemona_mixers[]= {
  /* ... */
  {
    .sysnr      = __NR_open,
    .in         = {
      .argnr    = 3,
      .extnr    = 0,
      .handlers = {
        { .dual = false , .blade = lemona_blade_string_null     },
        { .dual = false , .blade = lemona_blade_integer         },
        { .dual = false , .blade = lemona_blade_integer         },
      }
    },
    .out        = {
      .argnr    = 1,
      .extnr    = 1,
      .handlers = {
        { .dual = false , .blade = lemona_blade_integer         },
        { .dual = false , .blade = lemona_blade_string_fd       },
      },
    }
  },
  /* ... */
};
    \end{lstlisting}
    \caption{Lemona's Mixer Array}
    \label{listing:OpenMixer}
  \end{centering}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Controls

\section{Using Lemona}

\subsection{Installation}

Building \textbf{Lemona} is as simple as building any path for a
\textbf{Linux} kernel. All that need to be done is to:

\begin{itemize}
  \item switch to your kernel directory tree
  \item download the full patch
  \item apply the patch
  \item activate the Lemona feature in the config file % TODO see next listing
  \item compile and install the new kernel
\end{itemize}

\begin{verbatim}
$> cd $(PATH_TO_KERNEL_SRC)
$> wget http://lemona.googlecode.com/svn/trunk/patchs/patch-2.6.26.3
$> patch -p1 < patch-2.6.26.3
$> make menuconfig
$> make && make modules_install && make install
\end{verbatim}

\begin{verbatim}
  General Setup ->
    [*] Kernel->user space relay support (formerly relayfs)
    [ ] Configure standard kernel features (for small systems) ->
        -*- Load all symbols for debugging/ksymoops
        [*]   Include all symbol in kallsyms
  Kernel Hacking ->
    [*] Debug Filesystem
    [*] Kernel debugging
  Lemona ->
    <*> Enable Lemona
    [*]   Enable relaying of log to user-land
    (lemona) Name of the debugfs directory
    [*]   Transmit log via network
    (10.0.42.1) Server Address
    (4242)  Server Port
\end{verbatim}

\subsection{Loading}

If \textbf{Lemona} has been built as a module, it can be loaded using
the \verb=modprobe= or \verb=insmod= commands. Whatever build method
has been choose, the following informative messages will be displayed
upon loading and unloading.

\begin{verbatim}
$> cd $(PATH_TO_MODULES)
$> sudo insmod ./lemona.ko
$> dmesg | tail -2
 -==Lemona==- Initialization for kernel tree 2.6.26.3...
 -==Lemona==- Done.
$> sudo rmmod lemona
$> dmesg | tail -2
 -==Lemona==- Uninitializing...
 -==Lemona==- Done.
\end{verbatim}

\subsection{Fetching \& Analyzing the Logs}

When using \textbf{Lemona} with the \emph{net} module, a server is
needed in order to retrieve and store the \emph{zest} sent over the
network. A tool such a \textbf{netcat} can be used. Optionally, we
have developed a litte server named \emph{basket}. This server simply
collect the log and write them back to the local harddrive without
further processing.

For the analyze of the log, a simple script written in python
(\emph{picker.py}) can be found on the repositorie. For the moment, it
only allow to display the content off each \emph{zest} on the standard
output from which it is executed.

\begin{verbatim}
$> ./picker.py ../basket/
>>>Examining File ../basket/00000
        >>Parsing new entry at ../basket/00000:0
{'fsuid': 0, 'argnr': 2, 'egid': 0, 'usec': 471962171, 'uid': 0, 'tgid': 4153, 'args': ['\x01\x00\x00\x00', 't'], 'pid': 4153, 'argsz': [4, 1], 'fsgid': 0, 'exts': [], 'sysnr': 3, 'gid': 0, 'sec': 1226734216, 'euid': 0, 'extnr': 0, 'magic': 'ZeSt', 'extsz': [], 'parsed': 93, 'inout': 0, 'size': 93}
        <<Done
<<<Done
\end{verbatim}

% TODO
